package com.jp.algorithm;

public class BinarySearch {
    public static void binarySearch(int[] a, int n) {
        int left=searchLeft(a,0,a.length-1,n);
        int right=searchRight(a,0,a.length-1,n);
        System.out.println("left:"+left);
        System.out.println("right:"+right);
    }
    public static int searchLeft(int[] a, int start, int end, int n){

        if(start>end){
            return -1;
        }
        int mid=(end-start)/2 + start;
        if(a[mid] == n && (mid==0 || a[mid-1] < n)){
            return mid;
        }else if(a[mid] < n){
            return searchLeft(a,mid,end,n);
        }else{
            return searchLeft(a,start,mid,n);
        }
    }

    public static int searchRight(int[] a, int start, int end, int n){

        if(start>end){
            return -1;
        }
        int mid=(end-start)/2 + start;
        if(a[mid] == n && (mid==a.length-1 || a[mid+1] > n)){
            return mid;
        }else if(a[mid] > n){
            return searchRight(a,start,mid,n);
        }else{
            return searchRight(a,mid,end,n);
        }
    }

    public static  void test(){
        int[] a =  {6,7,8,8,8,8,10,11};
        binarySearch(a,8);
    }

    public static void main(String[] args) {
        test();
    }
}
